package com.formula.datastructure.question.tree;

// 线索二叉树 Threaded binary tree
// 线索化的目的是为了将空指针利用起来, 如果左右指针本身存在, 就不需要线索化
public class Quest07 {
    public static void main(String[] args) {
        Node07 root = new Node07(1);
        Node07 a1 = new Node07(42);
        Node07 a2 = new Node07(45);
        Node07 b1 = new Node07(39);
        Node07 b2 = new Node07(31);
        Node07 b3 = new Node07(35);


        Node07 c1 = new Node07(21);
        Node07 c2 = new Node07(34);

        root.left = a1;
        root.right = a2;

        a1.left = b1;
        a1.right = b2;
        a2.left = b3;

        b3.left = c1;
        b2.right = c2;

        Tree07 tree = new Tree07(root);
        tree.inOrderThread();
        System.out.println();
    }
}

class Tree07 {
    private Node07 root;
    public Node07 preNode;

    public Tree07(Node07 node) {
        root = node;
        preNode = null;
    }

    public void inOrderThread() {
        if (root != null) {
            inOrderThread(root);
        }
    }

    private void inOrderThread(Node07 node) {
        if (node.left != null) {
            inOrderThread(node.left);
        }

        if (node.left == null) {
            if (preNode != null) {
                node.leftType = 1;
                node.left = preNode;

                preNode.rightType = 1;
                preNode.right = node;
            }
            preNode = node;
        } else if (preNode.right == null) {
            preNode.rightType = 1;
            preNode.right = node;
            preNode = node;
        }

        if (node.right != null) {
            inOrderThread(node.right);
        }
    }
}

class Node07 {
    public Integer data;
    // 0-child
    // 1-prev
    public int leftType;
    // 0-child
    // 1-next
    public int rightType;
    public Node07 left;
    public Node07 right;

    public Node07(Integer data) {
        leftType = 0;
        rightType = 0;
        left = null;
        right = null;
        this.data = data;
    }

    public Integer getData() {
        return data;
    }

    public void setData(Integer data) {
        this.data = data;
    }

    public void inOrderTraverse() {
        if (left != null) {
            left.inOrderTraverse();
        }
        visit();
        if (right != null) {
            right.inOrderTraverse();
        }
    }

    private void visit() {
        System.out.println(data);
    }
}
